﻿/**	@file		octree.hpp
 *	@date		(2011-07-09 22:00:06)/(2012-03-10 12:27:00)
 *-----------------------------------------------------------------------------
 *	@version	1.0.2.14
 *	@author		Nick Shallery	(nicknide@gmail.com)
 *	@copyright	YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.
 *-----------------------------------------------------------------------------
**/


#if			!defined(__LOLIX__SOLA__OCTREE__NICK__K_IN_G__)
#define		__LOLIX__SOLA__OCTREE__NICK__K_IN_G__

#if			!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)
	#include	"../lolix_type.h"
#endif	//	!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)

#if			!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)
	#include	"../toy/allocator.h"
#endif	//	!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_LIST__NICK__K_IN_G__)
	#include	"../toy/std_list.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_LIST__NICK__K_IN_G__)

#if			!defined(__LOLIX__SOLA__BOUNDS__NICK__K_IN_G__)
	#include	"./bounds.hpp"
#endif	//	!defined(__LOLIX__SOLA__BOUNDS__NICK__K_IN_G__)

#if			!defined(__LOLIX__SOLA__VEC__NICK__K_IN_G__)
	#include	"./vec.hpp"
#endif	//	!defined(__LOLIX__SOLA__VEC__NICK__K_IN_G__)

//   5 - 4 - 右后上
//  /|  /|
// 1 + 0 |
// | 6 + 7 - 右后下
// |/  |/
// 2 - 3 - 右前下
namespace lolix{namespace sola{
	namespace _help{
		template<lx_i16 _OctreeLevel>
		struct _oct_num_sum
		{
			//	oct_num = ((1<<3*_OctreeLevel)-1)/7 : 因为移位可能会溢出的关系所以还是不用好了
#if			LOLIX_CFG__SUPPORT_CPP_0X
			enum:lx_u64 {oct_num = 8*_oct_num_sum<_OctreeLevel-1>::oct_num + 1};
#else	//	LOLIX_CFG__SUPPORT_CPP_0X
			const static lx_u64 oct_num = 8*_oct_num_sum<_OctreeLevel-1>::oct_num + 1;
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X
		};
		template<>
		struct _oct_num_sum<1>
		{
			enum{oct_num=1};
		};
		template<>
		struct _oct_num_sum<0>
		{
			enum{oct_num=1};
		};
	}
	template<typename _Ty /* 数据元素 */, typename _Tnum /* 坐标数据类型 */, size_type _MaxLevel /* 最大级别 */, typename _Talc = toy::allocator<void> >
	class octree_node
	{
		CANNT_COPY_LOLI;
		typedef octree_node<_Ty, _Tnum, _MaxLevel, _Talc> this_type;
	public:
		typedef typename _Talc::template rebind<this_type>::other allocator_type;
		typedef typename toy::size_info<_MaxLevel>::size_type	level_type;
		typedef toy::list<_Ty, allocator_type> data_container;
		typedef _Ty value_type;
		typedef _Tnum length_type;

		typedef typename data_container::const_iterator const_iterator;
		typedef typename data_container::iterator iterator;
		typedef typename data_container::const_reverse_iterator const_reverse_iterator;
		typedef typename data_container::reverse_iterator reverse_iterator;
		typedef typename lolix::toy::size_info<_help::_oct_num_sum<_MaxLevel>::oct_num>::size_type index_type;
		typedef aabb<_Tnum> area_type;
		typedef vec<3, _Tnum> position_type;

		template<typename _Tpalc>
		LOLIX_INLINE_CALL octree_node(area_type area, level_type lev, index_type idx, octree_node* pnt, _Tpalc alc)
			: _chr_obj_size(0), _pnt(pnt), _ref(1), _bound(area), _lev(lev), _data(alc), _idx(idx), _alc(alc)
		{
			for ( size_type i = 0; i != ARRAY_SIZE(_chr); )
			{
				_chr[i++] = 0;	_chr[i++] = 0;
				_chr[i++] = 0;	_chr[i++] = 0;
			}
		}
#if			LOLIX_CFG__SUPPORT_CPP_0X
		LOLIX_INLINE_CALL octree_node(octree_node&& o)
			: _chr_obj_size(o._chr_obj_size), _pnt(o._pnt), _ref(1), _bound(o._bound), _lev(o._lev), _data(o._alc), _idx(o._idx), _alc(o._alc)
		{
			for ( size_type i = 0; i != ARRAY_SIZE(_chr); )
			{
				_chr[i] = o._chr[i];++i;
				_chr[i] = o._chr[i];++i;
				_chr[i] = o._chr[i];++i;
				_chr[i] = o._chr[i];++i;
			}
		}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X

		LOLIX_INLINE_CALL ~octree_node(void)
		{
			for ( size_type i = 0; i != ARRAY_SIZE(_chr); ++i )
				if ( _chr[i] )
					_chr[i]->release();
		}

		LOLIX_INLINE_CALL size_type inc_ref(void)const
		{
			return ++_ref;
		}

		LOLIX_INLINE_CALL size_type release(void)const
		{
			if ( --_ref )
				return _ref;
			allocator_type alc(_alc);
			octree_node* pthis = const_cast<octree_node*>(this);
			alc.destroy(pthis);
			alc.deallocate(pthis, 1);
			return 0;
		}

		LOLIX_INLINE_CALL index_type index(void)const
		{
			return _idx;
		}

		octree_node* parent(void){return _pnt;}
		const octree_node* parent(void)const{return _pnt;}
		octree_node* chr(size_type i){return _chr[i];}
		const octree_node* chr(size_type i)const{return _chr[i];}

		LOLIX_INLINE_CALL bool empty(void)const
		{
			return !_chr_obj_size && _data.empty();
		}

		LOLIX_INLINE_CALL bool self_empty(void)const
		{
			return _data.empty();
		}

		LOLIX_INLINE_CALL size_type size(void)const
		{
			return _chr_obj_size + _data.size();
		}

		LOLIX_INLINE_CALL size_type self_size(void)const
		{
			return _data.size();
		}

		LOLIX_INLINE_CALL iterator begin(void)
		{
			return _data.begin();
		}

		LOLIX_INLINE_CALL const_iterator begin(void)const
		{
			return _data.begin();
		}

		LOLIX_INLINE_CALL iterator end(void)
		{
			return _data.end();
		}

		LOLIX_INLINE_CALL const_iterator end(void)const
		{
			return _data.end();
		}

		LOLIX_INLINE_CALL reverse_iterator rbegin(void)
		{
			return _data.rbegin();
		}

		LOLIX_INLINE_CALL const_reverse_iterator rbegin(void)const
		{
			return _data.rbegin();
		}

		LOLIX_INLINE_CALL reverse_iterator rend(void)
		{
			return _data.rend();
		}

		LOLIX_INLINE_CALL const_reverse_iterator rend(void)const
		{
			return _data.rend();
		}

#if			LOLIX_CFG__SUPPORT_CPP_0X
		template<typename _Tx, typename _Tp>
		LOLIX_INLINE_CALL void for_each_active(_Tx& tx, _Tp&& tp)
		{
			if ( this->empty() )
				return;

			if ( !tx(this, _bound, lolix::forward<_Tp>(tp)) )
				return;

#define		__LOLIX_TMP_DEF__FOR_EACH_NODE(idx)	if ( _chr[idx] ) _chr[idx]->for_each_active(tx, tp);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(0);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(1);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(2);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(3);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(4);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(5);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(6);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(7);
#undef		__LOLIX_TMP_DEF__FOR_EACH_NODE
		}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X

		template<typename _Tshape>
		LOLIX_INLINE_CALL bool is_contain(_Tshape const& sp)const
		{
			return check_intersection(_bound, sp) == INTERSECTION_TYPE_INCLUDE;
		}

		template<typename _Tshape>
		LOLIX_INLINE_CALL bool is_inner_contain(_Tshape const& sp)const
		{
			area_type atype;
			atype.min_pos(area_type::position_type(0, 0, 0));
			atype.size(_bound.size());
			return check_intersection(atype, sp) == INTERSECTION_TYPE_INCLUDE;
		}

		template<typename _Tshape>
		LOLIX_INLINE_CALL octree_node* inner_insert(vec<3, _Tnum>* io_inner_pos, _Ty const& obj, _Tshape const& obj_shape)
		{
			octree_node* last_node = __Inner_insert(io_inner_pos, obj, obj_shape, this);
			octree_node* node = last_node;
			while ( node->_pnt )
			{
				node = node->_pnt;
				++node->_chr_obj_size;
			}

			return last_node;
		}

		template<typename _Tshape>
		LOLIX_INLINE_CALL static octree_node* __Inner_insert(vec<3, _Tnum>* io_inner_pos, _Ty const& obj, _Tshape const& obj_shape, octree_node* node_cur)
		{
			auto finshape(obj_shape);
			area_type base_bound;
			base_bound.min_pos(0, 0, 0);
			for ( ; true; node_cur = node_cur->_pnt )
			{
				base_bound.size(node_cur->_bound.size());
				if ( check_intersection(base_bound, finshape) != INTERSECTION_TYPE_INCLUDE )
				{
					if ( !node_cur->_pnt )
					{
						node_cur->_data.push_back(obj);
						return node_cur;
					}
				}
				else
				{
					auto rtv = node_cur->__Try_inner_insert_chr(io_inner_pos, obj, obj_shape);
					if ( rtv )
						return rtv;
				}

				//	相差
				const auto distance = node_cur->_pnt->_bound.min_pos() - node_cur->_bound.min_pos();
				finshape.move(distance);
				*io_inner_pos += distance;
			}
		}

		template<typename _Tshape>
		LOLIX_INLINE_CALL octree_node* insert(_Ty const& obj, _Tshape const& obj_shape)
		{
			this_type* ptr_rtv;
			//	如果在自己的区域内
			const auto& min_pos = _bound.min_pos();
			const auto hsize = _bound.size()/(_Tnum)2;
#define		__LOLIX_TMP_DEF__FOR_EACH_NODE(idx, pos_x, pos_y, pos_z)	\
			if ( _chr[idx] )\
			{\
				if ( _chr[idx]->is_contain(obj_shape) )\
				{\
					ptr_rtv = _chr[idx]->insert(obj, obj_shape);\
					break;\
				}\
			}\
			else\
			{\
				area_type chr_aabb(\
					typename area_type::position_type(min_pos.x pos_x, min_pos.y pos_y, min_pos.z pos_z), hsize);\
					/*area_type chr_aabb;*/\
				if ( check_intersection(chr_aabb, obj_shape) == INTERSECTION_TYPE_INCLUDE )\
				{\
					octree_node* node = __Get_tree_node<idx>(hsize);\
					ptr_rtv = node->insert(obj, obj_shape);\
					break;\
				}\
			}

			LOLIX_DEF__ENTER_SECTION();
			{
				__LOLIX_TMP_DEF__FOR_EACH_NODE(0, +hsize.x	, +hsize.y	, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(1,			, +hsize.y	, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(2,			,			, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(3, +hsize.x	,			, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(4, +hsize.x	, +hsize.y	,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(5,			, +hsize.y	,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(6,			,			,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(7, +hsize.x	,			,			);
#undef		__LOLIX_TMP_DEF__FOR_EACH_NODE
				_data.push_back(obj);
				return this;
			}
			LOLIX_DEF__LEAVE_SECTION();

			++_chr_obj_size;
			return ptr_rtv;
		}

		LOLIX_INLINE_CALL bool remove(_Ty const& obj)
		{
			for ( auto it = _data.begin(); it != _data.end(); ++it )
			{
				if ( *it != obj )
					continue;
				_data.erase(it);
				return true;
			}

			return false;
		}
/*
		template<typename _Tshape>
		LOLIX_INLINE_CALL size_type remove(_Ty const& obj, _Tshape obj_shape)
		{
			_Tnum v = space.w/(_Tnum)2;
			size_type ptr_rtv = 0;
			//	如果在自己的区域内

			for ( auto it = _data.begin(); it != _data.end(); ++it )
			{
				if ( *it != obj )
					continue;

				_data.erase(it);
				++ptr_rtv;
				break;
			}

			if ( _chr_obj_size )
			{
				//	在父节点而不在子节点判断，因为根节点可能挂上不属于自己的节点数据
#define		__LOLIX_TMP_DEF__FOR_EACH_NODE(idx)	\
				if ( _chr[idx] && _chr[idx]->is_contain(obj_shape) )\
					ptr_rtv += _chr[idx]->remove(obj, obj_shape);

				__LOLIX_TMP_DEF__FOR_EACH_NODE(0);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(1);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(2);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(3);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(4);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(5);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(6);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(7);
#undef		__LOLIX_TMP_DEF__FOR_EACH_NODE
			}

			return ptr_rtv;
		}
*/
		LOLIX_INLINE_CALL const area_type& get_area(void)const{return _bound;}
		LOLIX_INLINE_CALL level_type get_level(void)const{return _lev;}
		LOLIX_INLINE_CALL index_type get_index(void)const{return _idx;}

	private:

		template<typename _Tshape>	//	尝试用内部坐标插入节点内
		LOLIX_INLINE_CALL octree_node* __Try_inner_insert_chr(vec<3, _Tnum>* io_inner_pos, _Ty const& obj, _Tshape const& obj_shape)
		{
#define		__LOLIX_TMP_DEF__FOR_EACH_NODE(idx, pos_x, pos_y, pos_z, npos_x, npos_y, npos_z)	\
			do{\
				auto finshape(obj_shape);\
				const vec<3, _Tnum> pos(0 npos_x, 0 npos_y, 0 npos_z);\
				finshape.move(pos);\
				if ( _chr[idx] )\
				{\
					if ( !_chr[idx]->is_inner_contain(finshape) )\
						break;\
					if ( io_inner_pos )\
						*io_inner_pos += pos;\
					return _chr[idx]->__Try_inner_insert_chr(io_inner_pos, obj, finshape);\
				}\
				else\
				{\
					if ( check_intersection(chr_area, finshape) != INTERSECTION_TYPE_INCLUDE )\
						break;\
					if ( io_inner_pos )\
						*io_inner_pos += pos;\
					auto node = __Get_tree_node<idx>(hsize);\
					if ( (node = node->__Try_inner_insert_chr(io_inner_pos, obj, finshape)) != 0 )\
						return node;\
				}\
			}while(0)

			const auto hsize = _bound.size()/(_Tnum)2;
			area_type chr_area;
			chr_area.min_pos(0, 0, 0);
			chr_area.size(hsize);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(0, +hsize.x	, +hsize.y	, +hsize.z	, -hsize.x	, -hsize.y	, -hsize.z	);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(1,			, +hsize.y	, +hsize.z	,			, -hsize.y	, -hsize.z	);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(2,			,			, +hsize.z	,			,			, -hsize.z	);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(3, +hsize.x	,			, +hsize.z	, -hsize.x	,			, -hsize.z	);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(4, +hsize.x	, +hsize.y	,			, -hsize.x	, -hsize.y	,			);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(5,			, +hsize.y	,			,			, -hsize.y	,			);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(6,			,			,			,			,			,			);
			__LOLIX_TMP_DEF__FOR_EACH_NODE(7, +hsize.x	,			,			, -hsize.x	,			,			);
#undef		__LOLIX_TMP_DEF__FOR_EACH_NODE

			_data.push_back(obj);
			return this;
		}

		template<int _Idx>
		LOLIX_INLINE_CALL octree_node* __Get_tree_node(typename area_type::size_type const& hsize)
		{
			if ( _chr[_Idx] )
				return _chr[_Idx];
			auto pos = _bound.min_pos();
#define		__LOLIX_TMP_DEF__FOR_EACH_NODE(idx, pos_x, pos_y, pos_z)	\
			case idx: pos.x = pos.x pos_x;pos.y = pos.y pos_y;pos.z = pos.z pos_z;break

			switch ( _Idx )
			{
				__LOLIX_TMP_DEF__FOR_EACH_NODE(0, +hsize.x	, +hsize.y	, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(1,			, +hsize.y	, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(2,			,			, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(3, +hsize.x	,			, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(4, +hsize.x	, +hsize.y	,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(5,			, +hsize.y	,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(6,			,			,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(7, +hsize.x	,			,			);
			}
#undef		__LOLIX_TMP_DEF__FOR_EACH_NODE

			decltype(_bound) chr_bound(pos, hsize);
			_chr[_Idx] = _alc.allocate(1);
			_alc.construct(_chr[_Idx], octree_node(chr_bound, _lev + 1, ((_idx+1)<<3)+_Idx, this, _alc));
			return _chr[_Idx];
		}

		this_type*			_chr[8];
		this_type* const	_pnt;

		const area_type		_bound;
		const index_type	_idx;
		size_type			_chr_obj_size;	//	子对象的数量
		data_container		_data;
		mutable size_type	_ref;
		allocator_type		_alc;
		const level_type	_lev;	//	最高层级为 0
	};

	template<typename _Ty /* 数据元素 */, typename _Tnum /* 坐标数据类型 */, size_type _MaxLevel /* 最大级别 */, typename _Talc = toy::allocator<void> >
	class octree
	{
		CANNT_COPY_LOLI;
	public:
		typedef octree_node<_Ty, _Tnum, _MaxLevel, _Talc> node_type;
		typedef typename node_type::position_type	position_type;
		typedef typename node_type::index_type index_type;
		typedef typename _Talc::template rebind<node_type>::other	allocator_type;

		LOLIX_INLINE_CALL octree(aabb<_Tnum> const& bound): _bound(bound), _root(0){ }
		template<typename _Tpalc>
		LOLIX_INLINE_CALL octree(aabb<_Tnum> const& bound, _Tpalc alc): _bound(bound), _alc(alc), _root(0){ }

		LOLIX_INLINE_CALL ~octree(void)
		{
			if ( _root )
				_root->release();
		}

		LOLIX_INLINE_CALL void clear(void)
		{
			if ( !_root )
				return;
			_root->release();
			_root = 0;
		}

		LOLIX_INLINE_CALL bool empty(void)const
		{
			return !_root || _root->empty();
		}

		LOLIX_INLINE_CALL size_type size(void)const
		{
			return _root?_root->size():0;
		}

#if			LOLIX_CFG__SUPPORT_CPP_0X
		template<typename _Tx, typename _Tp>
		LOLIX_INLINE_CALL void for_each_active(_Tx& tx, _Tp&& tp)
		{
			if ( this->empty() )
				return;

			_root->for_each_active(tx, lolix::forward<_Tp>(tp));
		}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X

		template<typename _Tshape>
		LOLIX_INLINE_CALL node_type* insert(_Ty const& obj, _Tshape const& obj_shape)
		{	//	首先， 查看当前的 root 是否需要调整了
			if ( !_root )
			{
				node_type* node = _alc.allocate(1);
				_alc.construct(node, node_type(_bound, 0, 0, 0, _alc));
				_root = node;
			}

			node_type* ist_pos = _root->insert(obj, obj_shape);

			return ist_pos;
		}

		template<typename _Tshape>
		LOLIX_INLINE_CALL size_type remove(_Ty const& obj, _Tshape const& obj_shape)
		{
			if ( !_root )
				return 0;
			return _root->remove(obj, obj_shape);
		}

		LOLIX_INLINE_CALL void distance(position_type* out_val, node_type const* from, node_type const* to)
		{
			if ( from == to )
			{
				(*out_val)(0, 0, 0);
				return;
			}

			lolix::lx_u8 from_pos[_MaxLevel], to_pos[_MaxLevel];
			__Fill_pos(from_pos, from);
			__Fill_pos(to_pos, to);
			const node_type* min_node;
			if ( from->get_level() > to->get_level() )
				min_node = to;
			else
				min_node = from;

			lolix::size_type min_pos = min_node->get_level();
			//	查询到公共父节点
			lolix::size_type last_same_level = 0;
			for ( ; last_same_level != min_pos; ++last_same_level )
			{
				if ( from_pos[last_same_level] != to_pos[last_same_level] )
					break;
			}

			//	OK, 向上追朔到这个节点
			while ( min_node->get_level() != last_same_level )
				min_node = min_node->parent();

			//	分别计算相差距离
			position_type fp, tp;
			__Calc_distance(&fp, min_node->get_area().size(), from_pos + min_node->get_level(), from->get_level() - min_node->get_level());
			__Calc_distance(&tp, min_node->get_area().size(), to_pos + min_node->get_level(), to->get_level() - min_node->get_level());
			*out_val = tp - fp;
		}

		LOLIX_INLINE_CALL node_type* get_node(index_type idx)
		{
			node_type* nd = _root;
#if			LOLIX_CFG__IS_DEBUG
			const index_type old_idx = idx;
#endif	//	LOLIX_CFG__IS_DEBUG
			while ( idx )
			{
				if ( !nd )
					return 0;

				size_type pos = size_type(idx & 0x7);
				nd = nd->chr(pos);
				idx >>= 3;
				--idx;
			}

#if			LOLIX_CFG__IS_DEBUG
			LOLIX_ASSERT(nd->index() == old_idx, L"八叉树节点的索引(%I64u)不等于输入的索引(%I64u)", lx_u64(nd->index()), lx_u64(old_idx));
#endif	//	LOLIX_CFG__IS_DEBUG
			return nd;
		}

		LOLIX_INLINE_CALL const node_type* get_node(index_type idx)const
		{
			return const_cast<octree*>(this)->get_node(idx);
		}

	private:
		static LOLIX_INLINE_CALL void __Fill_pos(lolix::lx_u8 (&pos)[_MaxLevel], const node_type* node)
		{
			index_type idx = node->index();
			const size_type level = node->get_level() - 1;
			for ( lolix::size_type i = 0; i != node->get_level(); ++i )
			{
				pos[level-i] = lx_u8(idx & 0x7);
				idx >>= 3;
				--idx;
			}
		}

		LOLIX_INLINE_CALL void __Calc_distance(position_type* out_val, position_type from_size, lolix::lx_u8 const* pos, lolix::size_type pos_len)
		{
			(*out_val)(0, 0, 0);
			auto hsize = from_size;
			for ( lolix::size_type i = 0; i != pos_len; ++i )
			{
				hsize /= 2;
				//	拿到切换到子节点的相对偏移
				switch ( pos[i] )
				{
#define		__LOLIX_TMP_DEF__FOR_EACH_NODE(idx, pos_x, pos_y, pos_z)	\
				case idx:\
					out_val->x = out_val->x pos_x;\
					out_val->y = out_val->y pos_y;\
					out_val->z = out_val->z pos_z;\
					break
				__LOLIX_TMP_DEF__FOR_EACH_NODE(0, +hsize.x	, +hsize.y	, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(1,			, +hsize.y	, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(2,			,			, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(3, +hsize.x	,			, +hsize.z	);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(4, +hsize.x	, +hsize.y	,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(5,			, +hsize.y	,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(6,			,			,			);
				__LOLIX_TMP_DEF__FOR_EACH_NODE(7, +hsize.x	,			,			);
				}
#undef		__LOLIX_TMP_DEF__FOR_EACH_NODE
			}
		}

		aabb<_Tnum>	_bound;
		allocator_type _alc;
		node_type* _root;			//	根节点
	};
}}

#endif	//	!defined(__LOLIX__SOLA__OCTREE__NICK__K_IN_G__)
